class Solution {
public:
    int qksort(vector<int>& nums, int l, int r, int k)
    {
        if (l >= r)
        {
            return nums[l];
        }
        int a = rand();
        int key = nums[a % (r - l + 1) + l];
        int left = l - 1;
        int right = r + 1;
        int i = l;
        while (i < right)
        {
            if (nums[i] < key)
            {
                std::swap(nums[++left], nums[i++]);
            }
            else if (nums[i] == key)
            {
                i++;
            }
            else
            {
                std::swap(nums[--right], nums[i]);
            }
        }

        if (k <= (r - right + 1))
        {
            return qksort(nums, right, r, k);
        }
        else if (k <= (r - left))
        {
            return key;
        }
        else
        {
            return qksort(nums, l, left, k - (r - left));
        }
    }
    int findKthLargest(vector<int>& nums, int k) {
        srand(time(0));
        return qksort(nums, 0, nums.size() - 1, k);
    }
};